import com.vernhe.TreeSet;

import java.util.ArrayList;

/**
 * 349. 两个数组的交集
 *
 * 给定两个数组，编写一个函数来计算它们的交集。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 *
 * 示例 2：
 *
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[9,4]
 *
 *
 *
 * 说明：
 *
 *     输出结果中的每个元素一定是唯一的。
 *     我们可以不考虑输出结果的顺序。
 */
public class Solution_349 {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1.length == 0 || nums2.length == 0) {
            return new int[]{};
        }
        //存放结果
        ArrayList<Integer> list = new ArrayList<>();

        // 初始化长短数组
        int[] shortArray,longArray;
        if (nums1.length < nums2.length) {
            shortArray = nums1;
            longArray = nums2;
        } else {
            shortArray = nums2;
            longArray = nums1;
        }

        // 将长度短的数组的元素放入set中
        TreeSet<Integer> set = new TreeSet<>();;
        for (int i = 0; i < shortArray.length; i++) {
            set.add(shortArray[i]);
        }

        // 遍历长的数组，如果有重复的则将其放入Result中去
        for (int i = 0; i < longArray.length; i++) {
            if (set.contains(longArray[i])) {
                list.add(longArray[i]);
                set.remove(longArray[i]);
            }
        }

        //初始化结果
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }

        return result;
    }
}
